package _树;

import java.util.*;
import java.util.function.BiFunction;

public class tree {

    // 589:N叉树的前序遍历：https://leetcode.cn/problems/n-ary-tree-preorder-traversal/
    public List<Integer> preorder(Node root) {
        ArrayList<Integer> res_pre = new ArrayList<>();
        travse(root, res_pre);
        return res_pre;
    }

    private void travse(Node root, List res_pre) {
        if (root == null) {
            return;
        }
        res_pre.add(root.val);
        for (Node ch : root.children) {
            travse(ch, res_pre);
        }
    }

    // 590:N叉树的后序遍历 https://leetcode.cn/problems/n-ary-tree-postorder-traversal/description/
    public List<Integer> postorder(Node root) {
        ArrayList<Integer> res_post = new ArrayList<>();
        travse1(root, res_post);
        return res_post;
    }

    private void travse1(Node root, List res_post) {
        if (root == null) {
            return;
        }
        for (Node ch : root.children) {
            travse1(ch, res_post);
        }
        res_post.add(root.val);
    }

    // 429：N叉树的层序遍历 https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
    // 637：层平均值
    // 199：二叉树的右视图
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<Node> q = new ArrayDeque<>();
        if (root == null) return ans;
        q.offer(root);
        // 向下走，每次处理下一层
        while (!q.isEmpty()) {
            int n = q.size();
            ArrayList<Integer> list = new ArrayList<>();
            // 遍历当前层的节点
            for (int i = 0; i < n; i++) {
                Node node = q.poll();
                list.add(node.val);
                // 把下一层的节点加入队列中
                for (Node child : node.children) {
                    q.offer(child);
                }
            }
            ans.add(list);
        }
        return ans;
    }
    // 103：二叉树的锯齿形层序遍历：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Deque<TreeNode> q = new ArrayDeque<>();
        boolean even = false;
        q.add(root);

        while (!q.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.pop();
                list.add(node.val);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            if (even)
                Collections.reverse(list);
            res.add(list);
            even = !even;
        }
        return res;
    }


    // 递归三部曲：
    // 第一步：确定递归函数的参数和返回值
    // 第二步：确定终止条件
    // 第三步：确定单层递归逻辑
    //
    // 二叉树的最大高度
    // 定义递归函数 maxDepth表示对于给定根节点的二叉树，返回当前最大深度
    public int maxDepth(TreeNode root) {
        // 递归终止条件
        if (root == null)
            return 0;
        // 单层递归逻辑
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return Math.max(l, r) + 1;
    }

    // 543 二叉树的最大直径：https://leetcode.cn/problems/diameter-of-binary-tree/description/
    // 在遍历的过程中 去对每个节点求最大直径
    int res = 0, temp = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    // 注意dfs还是在求最大深度
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        temp = l + r;
        res = Math.max(res, temp);
        return Math.max(l, r) + 1;
    }

    // 111：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
    // 最小深度递归解法：根据递归函数的定义，对某一个节点进行什么操作，其他的交给递归函数
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        // 单层递归逻辑
        int l = minDepth(root.left);
        int r = minDepth(root.right);
        // 后序位置
        if (root.left == null)
            return 1 + r;
        if (root.right == null)
            return 1 + l;
        return Math.min(l, r) + 1;
    }

    // 100:相同的树 https://leetcode.cn/problems/same-tree/submissions/511348486/
    // 递归
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p != null && q != null && p.val == q.val) {
            // 左子树相同 && 右子树相同
            boolean l = isSameTree(p.left, q.left);
            boolean r = isSameTree(p.right, q.right);
            return l && r;
        }
        return false;
    }

    // 257 二叉树的所有路径：https://leetcode.cn/problems/binary-tree-paths/
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ret = new ArrayList<>();
        solve(root, "", ret);
        return ret;
    }

    public void solve(TreeNode root, String cur, List<String> ret) {
        if (root == null)
            return;
        cur += root.val;
        if (root.left == null && root.right == null) {
            ret.add(cur);
        } else {
            solve(root.left, cur + "->", ret);
            solve(root.right, cur + "->", ret);
        }
    }

    // 129：求根节点到叶子节点之和：https://leetcode.cn/problems/sum-root-to-leaf-numbers/
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return dfs(root.left, sum) + dfs(root.right, sum);
    }

    // 101 对称二叉树 https://leetcode.cn/problems/symmetric-tree/
    public boolean isSymmetric1(TreeNode root) {
        return Symmetric1(root.left, root.right);
    }
    private boolean Symmetric1(TreeNode l, TreeNode r) {
        if (l == null && r != null) return false;

        if (l != null && r == null) return false;

        if (l == null && r == null) return true;
        if (l.val != r.val) return false;
        // 比较外侧
        boolean ww = Symmetric1(l.left, r.right);
        // 比较里侧
        boolean ll = Symmetric1(l.right, r.left);

        return ww && ll;
    }

    // 617:合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 递归终止条件
        if (root1 == null && root2 == null) return null;

        if (root1 == null) return root2;
        if (root2 == null) return root1;

        return new TreeNode(root1.val + root2.val,
                mergeTrees(root1.left, root2.left),
                mergeTrees(root1.right, root2.right));
    }

    // 226：翻转二叉树：层序遍历解法
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            TreeNode l = node.left;
            node.left = node.right;
            node.right = l;
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null)
                q.offer(node.right);
        }
        return root;
    }

    //404：左叶子之和:https://leetcode.cn/problems/sum-of-left-leaves/
    boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }

    // 版本2：用递归函数存取返回值(累加结果)
    public int dfs4(TreeNode node) {
        if (node == null) return 0;
        int ans = 0;
        if (node.left != null) {
            ans += isLeaf(node.left) ? node.left.val : dfs4(node.left);
        }
        if (node.right != null && !isLeaf(node.right)) {
            ans += dfs4(node.right);
        }
        return ans;
    }

    //1448 :统计二叉树中好节点的数目
    public int goodNodes(TreeNode root) {
        return dfs2(root, Integer.MIN_VALUE);
    }

    // pathMax表示 到 当前节点的路径最大值（放到参数里，随着递归进行更新）（所以一定是从上到下 的过程 来理解）
    // 递归函数返回值 记录当前节点及其子树中“好节点”的数量
    private int dfs2(TreeNode root, int pathMax) {
        if (root == null) return 0;
        int ans = 0;
        if (root.val >= pathMax) {
            ans++;
            pathMax = root.val;
        }
        // 子树中的”好节点“加上 当前节点的“好节点”数量
        ans += dfs2(root.left, pathMax) + dfs2(root.right, pathMax);
        return ans;
    }

    // 113:路径总数2，回溯
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res1 = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        back(root, 0, targetSum, res1, path);
        return res1;
    }

    // 进入节点、离开节点需要对路径进行选择、撤销选择
    private void back(TreeNode root, int currSum, int targetSum, List<List<Integer>> res1, List<Integer> path) {
        if (root == null) return;
        // 前序位置：做选择
        currSum += root.val;
        path.add(root.val);
        if (root.left == null && root.right == null && currSum == targetSum)
            res1.add(new ArrayList<>(path));
        if (root.left != null) {
            back(root.left, currSum, targetSum, res1, path);
            //撤销选择
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            back(root.right, currSum, targetSum, res1, path);
            path.remove(path.size() - 1);
        }
    }

    // 654：构造最大二叉树：https://leetcode.cn/problems/maximum-binary-tree/submissions/610921054/
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    public TreeNode build(int[] num, int l, int r) {
        if (l > r)
            return null;
        // 最大数极其对应的索引
        int index = 0, maxVal = Integer.MIN_VALUE;
        for (int i = l; i <= r; i++) {
            if (num[i] > maxVal) {
                maxVal = num[i];
                index = i;
            }
        }
        // 构造出根节点，然后递归构造左右子树
        TreeNode root = new TreeNode(maxVal);
        root.left = build(num, l, index - 1);
        root.right = build(num, index + 1, r);
        return root;
    }

    //===================================================================================
    //===================================================================================
    // 构造二叉树  草稿纸上把序列写出来，举个例子，，看着写代码就行了
    // 105 ：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd) return null;
        int rootV = preorder[preStart];
        int rootIndex = valToIndex.get(rootV);
        int leftSize = rootIndex - inStart;
        TreeNode root = new TreeNode(rootV);
        root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
        return root;
    }


}



















